package zcjq.d825;

import java.util.ArrayList;
import java.util.List;

public class Solution {

    private int minLen = Integer.MAX_VALUE;

    public int solution(int[][] board) {
        if (board == null || board.length <= 1) {
            return 0;
        }
        minLen = Integer.MAX_VALUE;
        backTrack(board, 0, 0, new ArrayList<>());
        return minLen;
    }


    private void backTrack(int[][] board, int x, int y, List<int[]> saved) {
        saved.add(new int[]{x, y});
        if (x == board.length - 1 && y == board.length - 1) {
            int total = 0;
            for (int i = 0; i < (saved.size() - 1); i++) {
                int[] pos = saved.get(i);
                total += board[pos[0]][pos[1]];
            }
            if (total < minLen) {
                minLen = total;
            }
        } else {
            int[][] directions = new int[][]{
                    {0, 1}, //右
                    {1, 0} //下
            };
            for (int[] direct : directions) {
                int newX = x + direct[0];
                int newY = y + direct[1];
                if (newX <= board.length && newY <= board[0].length) {
                    backTrack(board, newX, newY, saved);
                }
            }
        }
        saved.remove(saved.size() - 1);
    }

    public static void main(String[] args) {
        int[][] board = new int[][]{
                {5, 5, 7},
                {6, 7, 8},
                {2, 2, 4}
        };
        int solution = new Solution().solution(board);
        System.out.println(solution);
    }

}
